10. Conversia structurilor de date
10.1 Conceptul de conversie si necesitatea
10.2 Conversia directa
10.3 Conversia indirecta
10.4 Conversia structurilor de date statice
10.5 Conversia structurilor de date dinamice
10.6 Conversia structurilor de date mixte
back data structures curricula
10.1Conceptul de conversie si necesitate
Se considera structurile de date S1, S2, S3, ....,Sn.
Daca intr-un program este dominanta structura Sk, se impune ca celelalte structuri utilizate sa fie inlocuite cu structuri de forma dominanta.
De aceea este necesar sa se scrie proceduri care preiau informatia utila din structura Si si o copiaza in elemente ce corespund structurii Sj.
Conversia de structuri de date corespune acestui proces.
Se vorbeste despre conversia de matrice in fisier, care inseamna de fapt copierea elementelor matricei intr-un fisier.
Conversia unei liste duble intr-un fisier revine la a copia informatia utila din lista dubla in fisier.
Conversia unui fisier in graf inseamna construirea unui graf cu:
- informatia utila existenta in fisier
- legaturile dintre noduri, de asemenea, informatii stocate in fisier.
....................
....................
....................
....................
....................
....................
....................
....................
revenire
10.2Conversia directa
Conversia celor n structuri de date presupune existenta a n2-n proceduri care realizeaza conversia de la structura Si la structura Sj, i!=j, i,j =1,2,3,...,n.
....................
....................
....................
....................
....................
....................
....................
....................
revenire
10.3 Conversia indirecta
Se considera o structura de baza Sb si n-1 proceduri care executa conversii de la S1, S2, S3, ...., Sb-1, Sb+1, ....., Sn catre structura Sb. Se considera n-1 proceduri care executa conversii de la structura Sb catre celelate structuri.
In total sunt necesare 2*(n-1) proceduri nu n2-n proceduri ca in cazul conversiei directe.
Pentru a face conversia de la structura Si la structura Sj, este necesar sa se efectueze conversia in doi pasi si anume:
- conversia de la Si la structura Sb
- conversia de la Sb la structura Sj.
....................
....................
....................
....................
....................
....................
....................
....................
revenire
10.4 Conversia structurilor de date statice
Este o operatie de copiere.
Conversie de la vector la matrice.
Conversie de la vector spre fisier.
Conversie de la fisier spre vector.
Conversie de la fisier spre matrice.
Conversia de fisiere presupune:
- schimbarea organizarii
- schimbarea structurii articolului.
Pentru fiecare pereche de structuri statice se scrie o procedura de conversie.
Se are in vedere necomutativitatea operatiei.
Pentru fisiere, conversia trebuie sa aiba la baza o analiza completa, astfel incat procesul de conversie sa fie si eficient.
Se considera o colectivitate C formata din NC componente, c1, c2,c3,....,cNC,descrise prin sirurile de caractere sir1, sir2, sir3,...., sirNC.
Daca:
LG(sir1)=LG(sir2)=....=LG(sirNC)
rezulta ca fisierul are articole de lungime fixa.
Daca:
LG(sir1),LG(sir2),....,LG(sirNC)
apartin unei multimi formate din cateva elemente, rezulta ca fisierul are articole de lungime variabila.
Articolele din fisier contin doua campuri, unul care identifica tipul articolului si celalalt care contine de fapt informatia utila.
Daca lungimile articolelor sunt variabile aleatoare, se lucreaza cu fisier cu articole de lungime nedefinita.
Pentru a stabili cu ce tip de articole se definesc fisierele trebuie:
- sa se precizeze colectivitatea
- sa se incarce intr-un articole ca un sir compact toate datele referitoare la toate elementele colectivitatii
- sa se constituie multimea de subsiruri pentru elemente
- sa se calculeze lungimile subsirurilor
- sa se calculeze medii, dispersii, coeficienti de variatie
- sa se decida daca se lucreaza cu fisiere cu articole de lungime fixa, de lungime variabila sau de lungime nedefinita.
Pentru comportamentul dinamic al fisierelor trebuie pornit de la modurile de organizare.
Fisierele sunt organizate ca:
- fisiere secventiale
- fisiere indexate
- fisiere directe.
Se considera fisierul F cu articolele a1, a2, a3, ....., aNC , avand rangurile, respectiv, 1, 2, 3, ..., NC.
Pentru traversarea secventiala, rangurile articolelor sunt:
1, 2, 3, ..., NC.
Se calculeaza indicele agregat al rangurilor IAR, dat de relatia:
IAR=suma (i=1..NC)(rang_arti - rang_refi)2
Daca fisierul este secvential si este traversat in integralitatea sa, atunci:
rang_arti = rang_refi
si IAR = 0
Rezulta ca in cazul in care exista M rulari si se calculeaza pentru fiecare rulare un indice agregat IAR1, IAR2, IAR3, ....,IARM, se calculeaza si indicatorul mediu al agregarii rangurilor, ca medie aritmetica a acestor M ranguri.
Daca acest rezultat tinde catre zero, se prefera organizarea secventiala.
Daca fisierul F are articolele referite dupa chei, astfel incat rangurile de referire sunt:
- articolul a1 este referit ultimul, cu rang NC
- articolul a2 este referit ultimul, cu rang NC-1
- articolul a3 este referit ultimul, cu rang NC-2
......
- ultimul articol aNC este referit primul, cu rang 1.
Indicele acregat este dat de relatia:
IAGmax = 22*K*(K+1)*(2*K+)/3 daca NC=2*(K+1)
IAGmax = 22*K*(K+1)*(2*K+)/3 2*K daca NC=2*K
Rezulta ca:
0 mai mic decat IAR si IAR este mai mic decat IARmax
Daca IAR este cu valoare apropiata de IARmax/2 se va lucra cu fisiere indexat secventiale.
....................
....................
....................
....................
....................
....................
....................
....................
revenire
10.5Conversia structurilor de date dinamice
Se scriu proceduri uzuale de conversie liste simple la liste duble si invers.
Conversiile arborilor oarecare spre arbori binari sunt benefice pentru folosirea procedurilor care prelucreaza arbori binari prentru ca:
- acopera toate operatiile
- sunt mai rapide
- sunt mai fiabile
- se regasesc in toate aplicatiile.
....................
....................
....................
....................
....................
....................
....................
....................
revenire
10.6Conversia structurilor de date mixte
Conversiile de la structuri dinamice spre fisiere sunt cele mai des folosite pentru a creste performanta aplicatiilor.br>
Se salveaza informatiile utile din structuri dinamice in fisiere sau se arhiveaza aceste informatii.
La inceput de interval, pentru a prelucra date se creaza structuri dinamice avand informatii utile campuri din articolele fisierelor.
....................
....................
....................
....................
....................
....................
....................
....................
revenire
